package NowCoder.DynamicPlanning;
import java.util.*;

/**
 * 链接：https://www.nowcoder.com/questionTerminal/d83721575bd4418eae76c916483493de
 * 来源：牛客网
 *
 * 最长上升子序列
 * 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
 * 广场上站着一支队伍，她们是来自全国各地的扭秧歌代表队，现在有她们的身高数据，请你帮忙找出身高依次递增的子序列。
 * 例如队伍的身高数据是（1、7、3、5、9、4、8），其中依次递增的子序列有（1、7），（1、3、5、9），（1、3、4、8）等，其中最长的长度为4。
 *
 * 输入描述:
 * 输入包含多组数据，每组数据第一行包含一个正整数n（1≤n≤1000）。
 *
 * 紧接着第二行包含n个正整数m（1≤n≤10000），代表队伍中每位队员的身高。
 *
 * 输出描述:
 * 对应每一组数据，输出最长递增子序列的长度。
 * 示例1
 * 输入
 * 7
 * 1 7 3 5 9 4 8
 * 6
 * 1 3 5 2 4 6
 * 输出
 * 4
 * 4
 */
public class 最长上升子序列_编程_2_7_13 {
    //TODO:请重新做这一道题目
    public static int findLongest2(int[] A, int n){
        int[] dp = new int[n];
        dp[0] = 1;

        int[] ends = new int[n];

        ends[0] = A[0];
        //右哨兵
        int right = 1;

        int maxLength = dp[0];
        for(int i = 1;i<n;i++){
            //二分查找第一个比自己大的数，替代之，如果没找到，写在后边
            int start = 0;
            int end = right-1;
            int resultPos = right;
            while(start <= end ){
                int mid = start + (end - start)/2;   //重要
                if(ends[mid]>=A[i]){
                    resultPos = mid;
                    end = mid - 1;
                }else
                    start = mid + 1;
            }
            ends[resultPos] = A[i];
            if(resultPos == right)
                right++;
            dp[i] = resultPos + 1;
            maxLength = Math.max(maxLength, dp[i]);
        }
        return maxLength;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            int n = sc.nextInt();
            int[] data = new int[n];
            for(int i = 0;i<n;i++){
                data[i] = sc.nextInt();
            }
            System.out.println(findLongest2(data, n));
        }
    }
}

